package com.sicheng.lc.周赛.分类.dp.字符串;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/8 20:09
 */
public class 最长理想子序列 {



    // 字符串套路：枚举字符
    // 子序列 + 相邻 = dp
    // dp状态定义问题通常和题目关联很大，一般求啥就咋定义
    //  dp[i,j] 前i个字符里对于是否纳入s[i] 组成的子序列最后一个字符为j的最大价值
    //  dp[i,j] = max{dp[i-1,c]} + 1

    static int n = 26;
    static int[] dp = new int[n];

    {
        Arrays.fill(dp, 0);
    }

    // 由于dp[i,j]只由dp[i-1,x]转移而来 ,dp数组可以压缩到一维
    public int longestIdealString(String s, int k) {
        for (int i = 0; i < s.length(); i++) {
            int j = s.charAt(i) - 'a';
            int l = Math.max(j - k, 0), r = Math.min(j + k, n - 1);
            int max = -1;
            for (int m = l; m <= r; m++) {
                max = Math.max(max, dp[m]);
            }
            dp[j] = Math.max(dp[j], max + 1);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }


}
